package com.lw.leetcode.back.b;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 773. 滑动谜题
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/2 9:25
 */
public class SlidingPuzzle {

    public static void main(String[] args) {
        SlidingPuzzle test = new SlidingPuzzle();

        // 1
//        int[][] arr = {{1,2,3}, {4,0,5}};

        // -1
//        int[][] arr = {{1,2,3}, {5,4,0}};

        // 5
//        int[][] arr = {{4,1,2}, {5,0,3}};

        // 14
        int[][] arr = {{3, 2, 4}, {1, 5, 0}};

        int i = test.slidingPuzzle(arr);
        System.out.println(i);

    }

    private Map<String, Integer> map = new HashMap<>();
    private LinkedList<String> linkedList = new LinkedList<>();
    private String end = "123450";

    public int slidingPuzzle(int[][] board) {
        char[] arr = new char[6];
        int i = 0;
        for (int[] ints : board) {
            for (int anInt : ints) {
                arr[i++] = (char) (anInt + '0');
            }
        }
        String st = String.valueOf(arr);
        if (st.equals(end)) {
            return 0;
        }
        linkedList.add(st);
        map.put(st, 0);
        while (!linkedList.isEmpty()) {
            int i1 = find();
            if (i1 > 0) {
                return i1;
            }
        }
        return -1;
    }

    private int find() {
        String poll = linkedList.poll();
        int step = map.get(poll);
        char[] chars = poll.toCharArray();
        if (chars[0] == '0') {
            int change = change(step, chars, 0, new int[]{1, 3});
            if (change > 0) {
                return change;
            }
        }
        if (chars[1] == '0') {
            int change = change(step, chars, 1, new int[]{0, 2, 4});
            if (change > 0) {
                return change;
            }
        }
        if (chars[2] == '0') {
            int change = change(step, chars, 2, new int[]{1, 5});
            if (change > 0) {
                return change;
            }
        }
        if (chars[3] == '0') {
            int change = change(step, chars, 3, new int[]{0, 4});
            if (change > 0) {
                return change;
            }
        }
        if (chars[4] == '0') {
            int change = change(step, chars, 4, new int[]{1, 3, 5});
            if (change > 0) {
                return change;
            }
        }
        if (chars[5] == '0') {
            int change = change(step, chars, 5, new int[]{2, 4});
            if (change > 0) {
                return change;
            }
        }
        return -1;
    }

    private int change(int step, char[] chars, int a, int[] arr) {
        for (int i : arr) {
            chars[a] = chars[i];
            chars[i] = '0';
            String str = String.valueOf(chars);
            if (str.equals(end)) {
                return step + 1;
            }
            if (!map.containsKey(str)) {
                map.put(str, step + 1);
                linkedList.add(str);
            }
            chars[i] = chars[a];
            chars[a] = '0';
        }
        return -1;
    }

}
